package com.pandy.code;

import java.util.*;

/**
 * @description: 二叉树遍历 -- 非递归方式
 * @author: panhong
 * @date: 2025/3/28
 */
public class Code11_BinaryTree_Traverse_NonRecursive {

    /**
     * 使用栈实现二叉树的前序遍历
     * 先压入头节点，栈顶出来记录cur
     * 有右子树压入右子树，有左子树压入左子树 （顺序不能反，先右后左）
     * @param root
     */
    public static void preorder(BinaryNode root) {
        if(root != null) {
            Stack<BinaryNode> stack = new Stack<>();
            // 先压入头节点
            stack.push(root);
            BinaryNode cur;
            while (!stack.empty()) {
                cur = stack.pop();
                System.out.print(cur.value + "  ");

                if(cur.right != null) {
                    stack.push(cur.right);
                }
                if(cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    }

    /**
     * 使用栈实现二叉树的中序遍历
     *
     * 先依次压入左边界到栈中，直到为null
     * 弹出栈顶记为cur，打印，找到右边界
     * @param root
     */
    public static void order(BinaryNode root) {
        if(root != null) {
            Stack<BinaryNode> stack = new Stack<>();

            BinaryNode cur = root;
            while (!stack.empty() || cur != null) {
                // 先依次压入左边界到栈中，直到为null
                if(cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    // 弹出栈顶记为cur，打印，找到右边界
                    cur = stack.pop();
                    System.out.print(cur.value + "  ");
                    cur = cur.right;
                }
            }
        }
    }

    public static List<Integer> order1(BinaryNode root) {
        List<Integer> list = null;
        if(root != null) {
            list = new ArrayList<>();
            Stack<BinaryNode> stack = new Stack<>();

            BinaryNode cur = root;
            while (!stack.empty() || cur != null) {
                // 先依次压入左边界到栈中，直到为null
                if(cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    // 弹出栈顶记为cur，打印，找到右边界
                    cur = stack.pop();
                    list.add(cur.value);
                    cur = cur.right;
                }
            }
        }
        return list;
    }

    /**
     * 使用2个栈实现二叉树的后序遍历
     *
     * 先压入头节点，栈顶出来记录cur，压入到另外一个栈help中
     * 有左子树压入左子树，有右子树压入右子树
     *
     * 最大依次出栈help，打印
     * @param root
     */
    public static void postorder(BinaryNode root) {
        if(root != null) {
            Stack<BinaryNode> stack = new Stack<>();
            Stack<BinaryNode> help = new Stack<>();

            stack.push(root);
            BinaryNode cur;
            while (!stack.empty()) {
                cur = stack.pop();
                help.push(cur);
                if(cur.left != null) {
                    stack.push(cur.left);
                }
                if(cur.right != null) {
                    stack.push(cur.right);
                }
            }

            while (!help.empty()) {
                System.out.print(help.pop().value + "  ");
            }
        }
    }

    /**
     * 按层遍历二叉树
     * 宽度优先遍历：使用队列
     * @param root
     */
    public static void level(BinaryNode root) {
        if(root != null) {
            Queue<BinaryNode> queue = new LinkedList<>();
            queue.add(root);

            BinaryNode cur;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                System.out.print(cur.value + "  ");

                if(cur.left != null) {
                    queue.add(cur.left);
                }
                if(cur.right != null) {
                    queue.add(cur.right);
                }
            }
        }
    }

    public static void main(String[] args) {
        BinaryNode n1 = new BinaryNode(1);
        BinaryNode n2 = new BinaryNode(2);
        BinaryNode n3 = new BinaryNode(3);
        BinaryNode n4 = new BinaryNode(4);
        BinaryNode n5 = new BinaryNode(5);
        BinaryNode n6 = new BinaryNode(6);
        BinaryNode n7 = new BinaryNode(7);
        BinaryNode n8 = new BinaryNode(8);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n4.left = n8;
        n3.left = n6;
        n3.right = n7;

        System.out.println("=========非递归方式：前序遍历二叉树=========");
        preorder(n1);

        System.out.println();
        System.out.println("=========非递归方式：中序遍历二叉树=========");
        order(n1);

        System.out.println();
        System.out.println("=========非递归方式：后序遍历二叉树=========");
        postorder(n1);

        System.out.println();
        System.out.println("=========按层遍历二叉树=========");
        level(n1);

        List<Integer> integers = order1(n1);
        for(Integer value : integers) {
            System.out.print(value + "");
        }
    }
}
